package com.hou.offer;


/**
 * @author ：hc
 * @date ：Created in 2021/1/19 14:46
 * @modified By：
 */
public class MediumJZ46 {
    /**
     * 孩子们的游戏（圆圈中最后剩下的数）
     * 每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。
     * HF作为牛客的资深元老,自然也准备了一些小游戏。
     * 其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。
     * 然后,他随机指定一个数m,让编号为0的小朋友开始报数。
     * 每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,
     * 从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,
     * 并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？
     * (注：小朋友的编号是从0到n-1)
     *
     * 如果没有小朋友，请返回-1
     *
     * 看题解写的
     * 约瑟夫环问题，精髓就是返回的是下标
     * 如果 n = 5, m = 3
     * f(n,m) 返回的最终不用表演的人的下标
     * 如果在 n，m的状态下，出队一个人，然后剩下 n-1，m
     * 0 1 2 3 4    f(5, 3) = 3
     * 2 出列
     * 3 4 0 1    f(4, 3) = 0
     * 如何让f(4, 3) 恢复到上一状态呢？
     * 我们可以让 f(4, 3) + 3 = f(5, 3)
     * f(4, 3) + 3的过程其实就是
     * 把去掉的数字补回来，然后右移m位
     * index: 0 1 2 3 4 5 6 7 8
     *        3 4 0 1 2
     *              3 4 0 1 2      右移发现溢出了，因为咱们下标最多到4，所以把溢出的放在前面
     *        0 1 2 3 4
     * 溢出循环的过程其实就是取模 f(5, 3) = (f(4, 3) + 3) % 5
     * 可得公式 f(n,m) = (f(n-1,m) + m) % n
     */

    public int LastRemaining_Solution(int n, int m) {
        // 排除没有小朋友的情况
        if (n <= 0) {
            return -1;
        }
        // 重点，如果n=1的时候，只有一个数，也就是这个不用表演的，所以下标肯定为0
        if (n == 1) {
            return 0;
        }
        return (LastRemaining_Solution(n-1,m) + m) % n;
    }

    /**
     * 记忆化递归
     * 自底向上求解
     * f(1) = 0
     * f(2) = (f(1) + m) % 2
     * f(3) = (f(2) + m) % 3
     * ...
     */
    public int LastRemaining_Solution1(int n, int m) {
        // 排除没有小朋友的情况
        if (n <= 0) {
            return -1;
        }
        int res = 0;
        for (int i=2; i<=n; i++) {
            res = (res + m) % i;
        }
        return res;
    }
}
